/**
 * @param {number[][]} mat
 * @return {number[]}
 */
export var findDiagonalOrder = function (mat) {
  let dir = 1
  let [i, j] = [0, 0]
  const [m, n] = [mat.length, mat[0].length]
  const ans = []
  while (i < m && j < n) {
    ans.push(mat[i][j])
    if (dir === 1) {
      if (i - 1 >= 0 && j + 1 < n) {
        i--
        j++
      } else if (j + 1 < n) {
        dir = 0
        j++
      } else {
        dir = 0
        i++
      }
    } else {
      if (i + 1 < m && j - 1 >= 0) {
        i++
        j--
      } else if (i + 1 < m) {
        dir = 1
        i++
      } else {
        dir = 1
        j++
      }
    }
  }
  return ans
}

/**
 * @param {number[][]} mat
 * @return {number[]}
 */
export var findDiagonalOrder2 = function (mat) {
  const ans = []
  const [m, n] = [mat.length - 1, mat[0].length - 1]
  let [ro, co] = [0, 0]
  for (let i = 0; i <= m + n; i++) {
    if (i % 2 === 0) {
      // 向上查找
      while (ro >= 0 && co <= n) {
        ans.push(mat[ro][co])
        ro--
        co++
      }
      if (co > n) ro += 2
    } else {
      // 向下查找
      while (ro <= m && co >= 0) {
        ans.push(mat[ro][co])
        ro++
        co--
      }
      if (ro > m) co += 2
    }

    ro = ro > m ? m : ro < 0 ? 0 : ro
    co = co > n ? n : co < 0 ? 0 : co
  }
  return ans
}
